/**
 * 旅行商问题（TSP）相关算法工具
 * - 欧几里得距离
 * - Held-Karp 动态规划（适用于 <= 15 个点）
 * - 遗传算法（GA） + 2-opt（适用于 > 15 个点）
 */

// 欧几里得距离（按用户要求，不使用球面距离）
export function euclideanDistance(a, b) {
  const dx = a.lng - b.lng
  const dy = a.lat - b.lat
  return Math.sqrt(dx * dx + dy * dy)
}

// 2-opt 本地优化：改良路径顺序，降低总长度
export function twoOpt(route, points) {
  const improvedRoute = route.slice()
  let improved = true
  const totalDist = (seq) => {
    let s = 0
    for (let i = 0; i < seq.length - 1; i++) {
      s += euclideanDistance(points[seq[i]], points[seq[i + 1]])
    }
    return s
  }
  while (improved) {
    improved = false
    for (let i = 1; i < improvedRoute.length - 2; i++) {
      for (let k = i + 1; k < improvedRoute.length - 1; k++) {
        const newRoute = improvedRoute.slice(0, i)
          .concat(improvedRoute.slice(i, k + 1).reverse())
          .concat(improvedRoute.slice(k + 1))
        if (totalDist(newRoute) + 1e-12 < totalDist(improvedRoute)) {
          improvedRoute.splice(0, improvedRoute.length, ...newRoute)
          improved = true
        }
      }
    }
  }
  return improvedRoute
}

// Held-Karp 动态规划：从固定起点出发，访问所有点（不回到起点）
// @param {Array<{lat: number, lng: number}>} points - 待访问的点
// @param {{lat: number, lng: number}} start - 起点
// @returns {number[]} - 访问点的索引顺序
export function heldKarpPath(points, start) {
  const n = points.length
  const N = 1 << n
  // dp[mask][j] = 从 start 出发访问 mask 集合，且以 j 结尾的最短距离
  const dp = Array.from({ length: N }, () => Array(n).fill(Infinity))
  const parent = Array.from({ length: N }, () => Array(n).fill(-1))

  // 初始化：从起点直接到 j
  for (let j = 0; j < n; j++) {
    console.log('1 << j:', 1 << j);
    
    dp[1 << j][j] = euclideanDistance(start, points[j])
    console.log('dp[1 << j][j]:', dp[1 << j][j])
  }
 
  for (let mask = 1; mask < N; mask++) {
    for (let j = 0; j < n; j++) {
      if (!(mask & (1 << j))) continue
      const prevMask = mask ^ (1 << j)
      if (prevMask === 0) continue
      for (let k = 0; k < n; k++) {
        if (!(prevMask & (1 << k))) continue
        const cand = dp[prevMask][k] + euclideanDistance(points[k], points[j])
        if (cand < dp[mask][j]) {
          dp[mask][j] = cand
          parent[mask][j] = k
        }
      }
    }
  }

  // 结束：在所有以 j 结束的路径中取最小
  const full = N - 1
  let bestEnd = 0
  let best = Infinity
  for (let j = 0; j < n; j++) {
    if (dp[full][j] < best) {
      best = dp[full][j]
      bestEnd = j
    }
  }

  // 回溯路径序列：返回访问点的索引顺序 [j0, j1, ...]
  const order = []
  let mask = full
  let cur = bestEnd
  while (cur !== -1) {
    order.push(cur)
    const p = parent[mask][cur]
    mask ^= 1 << cur
    cur = p
  }
  order.reverse()
  return order
}

// 简单遗传算法 + 2-opt：适用于点数较多时的近似解
export function gaTwoOpt(points, start, options = {}) {
  const n = points.length
  const popSize = options.popSize || 80
  const generations = options.generations || 200
  const mutationRate = options.mutationRate || 0.15

  const distanceOf = (seq) => {
    let d = euclideanDistance(start, points[seq[0]])
    for (let i = 0; i < seq.length - 1; i++) {
      d += euclideanDistance(points[seq[i]], points[seq[i + 1]])
    }
    return d
  }

  const randomRoute = () => {
    const arr = Array.from({ length: n }, (_, i) => i)
    for (let i = n - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1))
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
    }
    return arr
  }

  const crossover = (p1, p2) => {
    // 部分映射交叉（PMX）简化实现
    const a = Math.floor(Math.random() * n)
    const b = Math.floor(Math.random() * n)
    const [l, r] = [Math.min(a, b), Math.max(a, b)]
    const child = Array(n).fill(-1)
    for (let i = l; i <= r; i++) child[i] = p1[i]
    for (let i = 0; i < n; i++) {
      if (child[i] !== -1) continue
      for (let j = 0; j < n; j++) {
        const cand = p2[j]
        if (!child.includes(cand)) { child[i] = cand; break }
      }
    }
    return child
  }

  const mutate = (route) => {
    if (Math.random() > mutationRate) return route
    const i = Math.floor(Math.random() * n)
    const j = Math.floor(Math.random() * n)
    const nr = route.slice()
    ;[nr[i], nr[j]] = [nr[j], nr[i]]
    return nr
  }

  // 初始化种群
  let population = Array.from({ length: popSize }, () => twoOpt(randomRoute(), points))

  let bestRoute = population[0]
  let bestDist = distanceOf(bestRoute)

  for (let g = 0; g < generations; g++) {
    // 选择（锦标赛）
    const nextGen = []
    while (nextGen.length < popSize) {
      const a = population[Math.floor(Math.random() * popSize)]
      const b = population[Math.floor(Math.random() * popSize)]
      const p1 = distanceOf(a) < distanceOf(b) ? a : b
      const c = population[Math.floor(Math.random() * popSize)]
      const d = population[Math.floor(Math.random() * popSize)]
      const p2 = distanceOf(c) < distanceOf(d) ? c : d
      let child = crossover(p1, p2)
      child = mutate(child)
      child = twoOpt(child, points)
      nextGen.push(child)
    }
    population = nextGen
    // 记录最好解
    for (const r of population) {
      const dist = distanceOf(r)
      if (dist < bestDist) {
        bestDist = dist
        bestRoute = r
      }
    }
  }

  return bestRoute
}


